/**
 * 
 */
package com.jeearsenal.algorithm;

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import com.jeearsenal.ds.Operator;

/**
 * @author monika
 *
 */
public class Evaluator {
	public final Map<Operator, Integer> PRIORITY_MAP;

	/**
	 * Data Structure for Evaluator.
	 * Keeping the data structure in a separate inner class,
	 * Evaluator can be used as stateless class. Hence only
	 * one instance of Evaluator can serve the purpose. 
	 * 
	 * @author monika
	 *
	 */
	class EvaluatorDS {
		private Stack<Operator> operatorStack;
		private Stack<String> operandStack;
		public EvaluatorDS() {
			operandStack = new Stack<String>();
			operatorStack = new Stack<Operator>();
		}
	}

	public Evaluator() {
		PRIORITY_MAP = new HashMap<Operator, Integer>();
		PRIORITY_MAP.put(Operator.BRACKET, -1);
		PRIORITY_MAP.put(Operator.SUBSTRACTION, 0);
		PRIORITY_MAP.put(Operator.ADDITION, 1);
		PRIORITY_MAP.put(Operator.MULTIPLICATION,  2);
		PRIORITY_MAP.put(Operator.DIVISION, 3);
		PRIORITY_MAP.put(Operator.OF, 4);
		PRIORITY_MAP.put(Operator.UNARY_PLUS, 6);
		PRIORITY_MAP.put(Operator.UNARY_MINUS, 7);
	}

	/**
	 * to evaluate the given expression
	 * Assuming all legal characters in the input expression.
	 * 
	 * @param expression
	 * @return the value of the expression
	 */
	public String evaluate(String expression) throws ArithmeticException {
		EvaluatorDS ds = buildStacks(expression);
		String result = processStacks(ds);
		if(result.equals("+0") || result.equals("-0")){
			result = "0";
		}
		return result;
	}

	/**
	 * to scan the expression and 
	 */
	private EvaluatorDS buildStacks(String expression) throws ArithmeticException {
		if(expression == null || expression == ""){
			return null;
		}
		// the list of all operands and operators appeared in the order 
		List<String> opList = preprocess(expression);
		//System.out.println("oplist : "+opList);
		//System.out.println("Length of opList:"+opList.size());

		EvaluatorDS ds = new EvaluatorDS();
		for (int index=0; index< opList.size(); index++) {
			String op = opList.get(index);
			//System.out.println("index = "+index+" and OP="+op);
			if(isOperand(op)){
				ds.operandStack.push(op);
			}else{
				switch (op.charAt(0)) {
				case '+':
					/*
					 *  it can be unary or binary.
					 *  '+' is binary only if it is preceded by an operand or a closing parenthesis.
					 */
					if(index >= 1){
						String preOp = opList.get(index-1);
						if(isOperand(preOp) == true || preOp == ")"){
							// + is binary
							pushOperator(Operator.ADDITION, ds);
						}
					}				
					break;
				case '-':
					/*
					 *  it can be unary or binary.
					 *  '-' is binary only if it is preceded by an operand or a closing parenthesis.
					 */
					if(index >= 1){
						String preOp = opList.get(index-1);
						if(isOperand(preOp) == false && preOp != ")"){
							// - is unary
							pushOperator(Operator.UNARY_MINUS, ds);
						} else {
							// - is binary
							pushOperator(Operator.SUBSTRACTION, ds);
						}
					} else{
						pushOperator(Operator.UNARY_MINUS, ds);
					}				
					break;
				case '*':
					pushOperator(Operator.MULTIPLICATION, ds);				
					break;
				case '/':
					pushOperator(Operator.DIVISION, ds);				
					break;
				case '(':
					pushOperator(Operator.BRACKET, ds);				
					break;
				case ')':
					processClosingParenthesis(ds);				
					break;
				case 'O':
					pushOperator(Operator.OF, ds);				
					break;
				default:
					break;
				}
			}

		}
		return ds;
	}

	/**
	 * to precess the data structure built and find the final result.
	 * 
	 * @param ds - the Evalutor Data Structure.
	 * @return the value of the expression from which the ds object is built.
	 */
	private String processStacks(EvaluatorDS ds){
		//System.out.println("In processStack()");
		if(ds == null ){
			return null;
		}
		while(ds.operatorStack.isEmpty() == false){
			processOperand(ds);
		}
		try{
			String result = ds.operandStack.pop();
			if(ds.operandStack.isEmpty() == false){
				invalidExpression();
			}
			return result;
		}catch (EmptyStackException e) {
			invalidExpression();
		}

		return null;
	}

	private List<String> preprocess(String expression) {
		//System.out.println("In process()");
		if(expression != null){
			List<String> opList = new ArrayList<String>();
			final String regExp = "[+\\-*/()oO]";
			String [] strSplit = expression.split( regExp, 2);
			//System.out.println("Length of strSplit[]:"+strSplit.length);
			while(strSplit.length == 2){
				//System.out.println("strSplit[0]="+strSplit[0]+"\nstrSplit[1]="+strSplit[1]);
				int index = strSplit[0].length();
				if(index < expression.length()){
					String operator = "";
					switch (expression.charAt(index)) {
					case '+':
						operator = "+";
						break;
					case '-':
						operator = "-";
						break;
					case '*':
						operator = "*";
						break;
					case '/':
						operator = "/";
						break;
					case '(':
						operator = "(";
						break;
					case ')':
						operator = ")";
						break;
					case 'o':  case 'O':
						operator = "OF";
						/*
						 *  regular expression has just consumed 'o'.
						 *  we need to consume 'f' as well.
						 */
						strSplit[1] = strSplit[1].substring(1);
						break;
					default:
						// illegal character
						break;
					}
					if(!strSplit[0].trim().equals("")){
						opList.add(strSplit[0].trim()); // add the operand
					}
					opList.add(operator); // add the operator
					expression = strSplit[1].trim(); // remaining part of expression
				}
				strSplit = expression.split(regExp, 2);
			}
			if(strSplit.length == 1){
				if(!strSplit[0].trim().equals("")){
					opList.add(strSplit[0].trim()); // add the operand
				}
			}

			return opList;
		}
		return null;
	}

	/**
	 * to check if the 'value' is an operand.
	 * that is it represents a number.
	 * @param value
	 * @return
	 */
	private boolean isOperand(String value){
		//System.out.println("in isOperand()");
		if(value == "" || value == null){
			return false;
		}
		//System.out.println("Value:"+value);
		char firstChar = value.charAt(0);
		int n = firstChar - '0';
		if(n>=0 && n <= 9){
			return true;
		}
		return false;
	}


	private void pushOperator(Operator operator, EvaluatorDS ds){
		if(operator == Operator.BRACKET){
			ds.operatorStack.push(operator);
			return;
		}
		if(ds.operatorStack.isEmpty() == false){
			int priority = PRIORITY_MAP.get(operator).intValue();
			int pTop = PRIORITY_MAP.get(ds.operatorStack.peek());
			while(priority <= pTop && pTop >= 0){
				processOperand(ds);
				if(ds.operatorStack.isEmpty()){
					pTop = -1;
				}else{
					pTop = PRIORITY_MAP.get(ds.operatorStack.peek());
				}
			}
		}
		ds.operatorStack.push(operator);
	}


	private void processOperand(EvaluatorDS ds) {
		if(ds.operatorStack.isEmpty() == false){
			Operator op = ds.operatorStack.pop();
			String operand1="";
			try{
				operand1 = ds.operandStack.pop();
			}catch (EmptyStackException e) {
				invalidExpression();
			}
			if(op == Operator.UNARY_MINUS){
				ds.operandStack.push("-"+operand1);
			}else{
				String operand2 = "";
				try{
					operand2 = ds.operandStack.pop();
				}catch (EmptyStackException e) {
					invalidExpression();
				}
				SignedArithmeticOperations calculator = new SignedArithmeticOperations();
				String result = "";
				switch (op) {
				case ADDITION:
					result = calculator.add(operand2, operand1);
					break;
				case SUBSTRACTION:
					result = calculator.subtract(operand2, operand1);
					break;
				case MULTIPLICATION:
					result = calculator.multiply(operand2, operand1);
					break;
				case DIVISION:
					result = calculator.divide(operand2, operand1)[0];
					break;
				case OF:
					result = calculator.multiply(operand2, operand1);
					break;
				default:
					break;
				}
				ds.operandStack.push(result);
			}
		}

	}


	private void processClosingParenthesis(EvaluatorDS ds) {
		try{
			Operator op = ds.operatorStack.peek();
			while(op != Operator.BRACKET) {
				processOperand(ds);
				op = ds.operatorStack.peek();
			}
			if(op == Operator.BRACKET){
				ds.operatorStack.pop();
			}
		}catch(EmptyStackException e){
			invalidExpression();
		}
	}

	private void invalidExpression() throws ArithmeticException{
		throw new ArithmeticException("INVALID EXPRESSION.");
	}



}
